package com.study.algorithm;

/**
 * @Author tanglingyu
 * @Date: 2021/05/06/ 14:01
 * @Description
 * 普通递归-->尾递归-->汉诺塔问题
 */
public class Recursive {

  public static void main(String[] args) throws Exception {
    int i = func1(10);
    System.out.println(i);
    int j = func2(10, 1);
    System.out.println(j);
    hanio(3, "A", "B", "C");
  }

  /**
   * 普通递归
   *
   * @param n
   * @return
   * @throws Exception
   */
  private static int func1(int n) throws Exception {
    if (n <= 0) {
      throw new Exception("n不合法");
    }
    if (n == 1) {
      return 1;
    }
    return n * func1(n - 1);
  }

  /**
   * 尾递归
   *
   * @param n
   * @param res
   * @return
   * @throws Exception
   */
  private static int func2(int n, int res) throws Exception {
    if (n <= 0) {
      throw new Exception("n不合法");
    }
    if (n == 1) {
      return res * n;
    }
    return func2(n - 1, res * n);
  }


  /**
   * 汉诺塔问题递归算法
   *
   * @param n      问题规模
   * @param source 原盘子所在位置
   * @param target 目标盘子所在位置
   * @param temp   临时过渡盘子所在位置
   */
  private static void hanio(int n, String source, String target, String temp) {
    if (n == 1) {
      System.out.println("第" + n + "个盘子从" + source + "移动到" + target);
    } else {
      hanio(n - 1, source, temp, target);
      System.out.println("第" + n + "个盘子从" + source + "移动到" + target);
      hanio(n - 1, temp, target, source);
    }
  }
}
